1. Field of the Invention
The present invention generally relates to network route computation through autonomous or administrative domains and, more particularly, to an object oriented approach for controlling a network comprising sub-networks that employ different link-state control schemes, either because they are operated by different operators or because they comprise equipment from different vendors.
2. Description of the Prior Art
In large communication networks, such as the Internet, it is a challenging task to route a packet of data from one node to another. A network of this type often comprises many sub-networks which, in turn, are comprised of many nodes. These sub-networks are often of different and not necessarily compatible, such as, for example, token ring networks, wide area networks (WANs), and many different proprietary networks. Even if data formats are identical, control protocols for these networks are usually very different. To get a packet of data from Node A to Node B, it is conceivable that the data packet will have to pass through many different sub-network systems along the way. Hence, prior to sending the packet, the network controller (NC) at the originating Node A must package the packet with all of the proper routing and syntactical data to ensure that each system along the route understands what it is to do with the packet. Alternatively, in a connection oriented network, a route must be set across the network with different control schemes.
There are often many possible paths or routes connecting any two points or nodes through different sub-networks. Some paths may be faster, some longer, some shorter, and some less expensive than others. Hence, the path chosen may be a function of many parameters particular to the data being sent. This is sometimes referred to as quality of service (QoS) parameters. In many network control schemes, termed link-state routing, the particular path chosen is the job of the network controller (NC) at the originating node. Most network control standards for complex networks are based on "link-state" routing. That is, a replicated topology database representing the whole network exists in the NC at each node in the network. This permits the NC at the originating node to calculate an appropriate path and thereafter package the packet with all of the necessary routing data appropriate for that chosen path (source routing). Similarly, in a connection oriented network, NC packages a control message with this source route. The message notifies the different NCs along its route to set up a connection.
As sub-networks, sometimes referred to as .domains., are added to and removed from the network, the topology database at each node in the network is updated by passing control messages between the various nodes in the network. Such updates most notably include periodic topology and utilization updates.
In order to enable topology updates, a rigid standard or paradigm for the topological data has to specify a fixed structure for the messages (syntax), as well as how they should be understood by network control (i.e., its semantics). The most prominent examples for this paradigm is the Private Network-to-Network (PNNI) standard for inter-network control of asynchronous transfer mode (ATM), and the Open Shortest Path First (OSPF) standard for Internet intra-domain routing. In other words, the network controller (NC) must know the standards and control format for each sub-network within the network. Often times the various standards of the sub-networks vary greatly thus requiring the NC at each node to replicate many standards and protocols.
This problem has been addressed to some extent in, for example, U.S. Pat. No. 4,664,532 to George et al. which shows a method for automatic topology updating in a hybrid network. Selected nodes in the network are provided with extended memory and computing capabilities and each maintains a topology data base for the network. The other nodes in the network are provided with smaller memories and computing capabilities and maintain information related solely to the topology of the local sub-network. In this case, only the selected nodes need to be updated with network topology when a change in the network occurs.
A drawback of this rigid paradigm is that it is very hard to modify existing standards as technology evolves, since backward compatibility must be maintained. This is even true for proprietary protocols, since the whole sub-net must be upgraded simultaneously to enable interoperability. That is each time a new sub-network is added, each node in the network must be provided with the protocol. Alternatively, it is required to agree upon a single standard for network control. This process is very difficult and yields less than optimal control schemes that aim at the least common denominator.
The practice of topology aggregation is used in most of the standards and implementations of scalable networks. Topology aggregation refers to the reduction of complex topological data into smaller and simpler data which approximates the original data. A few examples of topology aggregation are the single level aggregation of Decnet (areas/hosts), the two level aggregation of IP (autonomous systems/networks/hosts), and the unbounded aggregation of the PNNI standard for ATM.
Several methods and schemes have been proposed for reducing the amount of data needed to be sent to the individual nodes during a network topology update. For example, U.S. Pat. No. 5,101,348 to Arrowood et al. describes a method for reducing the amount of data passed during topology updates. It assumes that all the nodes employ the same control mechanism and therefore does not address the case of integrating different control schemes into a single control plane.
Similarly, U.S. Pat. No. 5,265,092 to Soloway et al. focuses on providing a loop free, shortest path routing algorithm for data packets. It assumes that all the nodes employ the same control mechanism. However, Soloway does not address integrating different control schemes.
U.S. Pat. No. 5,509,123 to Dobbins shows an object oriented architecture or network layer routing which distributes function and system behavior in autonomous router objects. However, Dobbins only recognizes distance vector routing and is therefore not applicable to link-state routing suitable for connection oriented networks. As such, Dobbins enables different networks to co-exist without interaction but does not permit different networks to inter-operate.
Along a slightly different vein, U.S. Pat. No. 5,430,727 to Callon is directed to multiple protocol routing for networks which routs data from different protocols by the same routers, thereby sharing the router hardware as well as the topological data and updates.